<?php
/**
 * 将二叉搜索树由小到大进行迭代
 */
class MinToMixIterator implements Iterator
{
    /**
     * @var BinarySearchTree $tree
     */
    protected $tree=null;
    /**
     * @var array[] $stack 当前的迭代器的栈,每个元素是一个栈帧
     *  其中第一项是节点
     *  第二项是状态:0,当前;1,正在迭代左子树;2,正在迭代右子树
     *  第三行是当前索引值,只有栈顶的是正确的
     */
    protected $stack=[];
    protected $current_key=-1;
    protected $current_node=null;
    /**
     * @param BinarySearchTree $tree
     */
    public function __construct($tree)
    {
        $this->tree=$tree;
    }
    
    /**
     * 沿着堆栈向上回溯
     */
    protected function goUp()
    {
        $elem=array_pop($this->stack);
        //没有遍历过右子树
        if($elem[1]===1){
            $this->current_node=$elem[0];
            // $this->goRight($elem[0]);
        }
        //已经遍历过右子树
        else{
            $this->goUp();
        }
    }
    /**
     * 向右子树查找，找到右子树中的最左面的元素
     */
    protected function goRight($node)
    {
        if($node->right === null){
            $this->goUp($node);
        }
        else{
            $this->stack[]=[$node,2,0];
            $this->goLeft($node->right);
        }
    }
    /**
     * 向左子树查找，直到直到最左面的元素
     */
    protected function goLeft($node)
    {
        if($node->left === null){
            $this->current_node=$node;
        }
        else{
            $this->stack[]=[$node,1,0];
            $this->goLeft($node->left);
        }
    }

    public function current()
    {
        return $this->current_node->data;
    }
    public function key()
    {
        return $this->current_key;
    }
    public function next()
    {
        $this->current_key++;
        if(count($this->tree) > $this->current_key){
            $this->goRight($this->current_node);
        }
    }
    public function rewind()
    {
        $node=$this->tree->root;
        $this->stack=[];
        if($node !== null){
            $this->goLeft($node,0);
            $this->current_key=0;
        }
    }
    public function valid()
    {
        return count($this->tree) > $this->current_key;
    }
}
